import java.util.PriorityQueue;

public class Sort {
    // 插入排序
    public static void insertSort(int[] array) {
        //默认第一个是有序的
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i - 1;//这是看tmp插到哪里
            for (; j >= 0; j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }//这里j已经等于-1
            array[j + 1] = tmp;
        }
    }

    // 希尔排序
    public static void shellSort(int[] array) {
        int gap = (array.length - 1) / 2;
        while (gap > 1) {
            gap = gap / 2;
            for (int i = 1; i < array.length; i = i + gap) {
                int tmp = array[i];
                int j = i - gap;//这是看tmp插到哪里
                for (; j >= 0; j = j - gap) {
                    if (array[j] > tmp) {
                        array[j + gap] = array[j];
                    } else {
                        break;
                    }
                }//这里j已经等于-1
                array[j + gap] = tmp;
            }
        }
    }

    // 选择排序
    public static void selectSort1(int[] array) {
        //一次派出最小的元素
        for (int i = 0; i < array.length; i++) {
            int min = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[min]) {
                    min = j;
                }
            }
            if (min != i) {
                swap(array, i, min);
            }
        }
    }

    //同时找出最大值和最小值
    public static void selectSort2(int[] array) {
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            int min = left;
            int max = left;
            for (int i = left + 1; i <= right; i++) {
                if (array[i] < array[min]) {
                    min = i;
                }
                if (array[i] > array[max]) {
                    max = i;
                }
            }
            swap(array, min, left);
            if (max == left) {
                max = min;
            }
            swap(array, max, right);
            right--;
            left++;
        }
    }

    protected static void swap(int[] arr, int j, int k) {
        int tmp = arr[j];
        arr[j] = arr[k];
        arr[k] = tmp;
    }

    public static void heapSort1(int[] array) {
        //先建队
        createBigHeap(array);
        int end = array.length - 1;
        while (end > 0) {
            swap(array, 0, end);
            shiftDowm(array, 0, end);
            end--;
        }
    }

    //建队
    protected static void createBigHeap(int[] array) {
        for (int parent = (array.length - 1 - 1) / 2;
             parent >= 0; parent--) {
            shiftDowm(array, parent, array.length);
        }
    }

    public static void shiftDowm(int[] arr, int parent, int len) {
        int child = 2 * parent + 1;//左孩子的位置
        while (child < len) {
            if (child + 1 < len && arr[child] < arr[child + 1]) {
                child++;
            }
            if (arr[child] > arr[parent]) {
                swap(arr, child, parent);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    // 堆排序
    public static void heapSort(int[] array) {
        PriorityQueue<Integer> p1 = new PriorityQueue<>();
        for (int i = 0; i < array.length; i++) {
            p1.offer(array[i]);
        }
        for (int i = 0; i < array.length; i++) {
            array[i] = p1.poll();
        }
    }

    // 冒泡排序
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            boolean flag = true;
            for (int j = i; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    flag = false;
                }
            }
            if (flag == true) {
                break;
            }
        }
    }

    // 快速
    //Hoare版
    // 快速
    public static void quickSort(int[] array) {
        quickSortChild(array, 0, array.length - 1);
    }

    protected static void quickSortChild(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int index = partitionHoare(array,start,end);
        quickSortChild(array, start, index - 1);
        quickSortChild(array, index + 1, end);
    }

    //找基准点
    protected static int partitionHoare(int[] array, int left, int right) {
        int pivot = left;
        while (left < right) {
            while (left < right && array[right] >= array[pivot]) {
                right--;
            }
            //right下标的值 小于pivot
            while (left < right && array[left] <= array[pivot]) {
                left++;
            }
            //left下标的值 大于pivot
            swap(array, left, right);
        }
        //交换 和 原来的left
        swap(array, left, pivot);
        return left;
    }
}